package com.sicheng.lc.周赛.分类.dp;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/15 23:12
 */
public class 最大矩形 {
    //https://leetcode.cn/problems/maximal-rectangle/
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if (m == 0)
            return 0;
        int n = matrix[0].length;
        if (n == 0)
            return 0;


        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1')
                    dp[i][j] = 1;
            }
        }


        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] != 0) {
                    dp[i][j] += dp[i - 1][j];
                }
            }
        }

        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] == 0)
                    continue;
                int h = dp[i][j];
                for (int k = j; k >= 0 && dp[i][k] > 0; k--) {
                    h = Math.min(h, dp[i][k]);
                    max = Math.max(max, h * (j - k + 1));
                }
            }
        }


        return max;
    }
}
